board = [["C", "A", "A"], ["A", "A", "A"], ["B", "C", "D"]]
word = "AAB"

max_r = len(board) - 1
max_c = len(board[0]) - 1
word = list(word)

res = False
import pickle


def search(r, c, i, par_board):
    global res
    if res:
        return True
    import copy
    my_board = pickle.loads(pickle.dumps(par_board))
    # my_board = copy.deepcopy(par_board)
    if my_board[r][c] == word[i]:
        my_board[r][c] = '#'
        if i == len(word) - 1:
            res = True
            return True
        else:
            if r - 1 >= 0:
                search(r - 1, c, i + 1, my_board)
            if r + 1 <= max_r:
                search(r + 1, c, i + 1, my_board)
            if c - 1 >= 0:
                search(r, c - 1, i + 1, my_board)
            if c + 1 <= max_c:
                search(r, c + 1, i + 1, my_board)
    else:
        return False


for j in range(max_r + 1):
    for k in range(max_c + 1):
        if board[j][k] == word[0]:
            search(j, k, 0, board)
            if res:
                print(res)
            else:
                print(res)

print("False")
